#pragma once
#include <iostream>
#include <unordered_set>
#include <queue>
using namespace std;

struct TestGrady {

	SocialGraph* social_graph;
	list<pair<int, int>> com_topk;

	TestGrady(SocialGraph* social_graph) {
		this->social_graph = social_graph;
	}

	void pre_influence(unordered_set<int> target_user) {
		for (int id = 0; id < social_graph->node_num; id ++) {
			for (auto nei : social_graph->nodes[id]->socialOutEdge) {
				if (target_user.find(nei.first) == target_user.end()) continue; 
				if (nei.second > 0.5) {
					social_graph->nodes[id]->canInfulence.emplace(nei.first);
					social_graph->nodes[id]->binf++; 
					social_graph->nodes[nei.first]->beInfluence.emplace(id); 
				}
			}
		}
	}

	void findTopK(int k, unordered_set<int> target_user) { 
		pre_influence(target_user);
		set<int> init_set;
		std::list<std::pair<int, int>> kmax = Iteration(k, init_set); 
		if (kmax.size() == 0) return;
		init_set.emplace(kmax.begin()->first); 
		auto beg = kmax.begin();
		pair<int, int> temp = { beg->first , beg->second };
		com_topk.emplace_back(temp);
		change_Binf(beg->first);
		kmax.pop_front(); 

		while (init_set.size() < k) {
			auto beg = kmax.begin();
			auto behind = kmax.end();
			if ((--behind) == beg) {
				init_set.emplace(beg->first);
				temp = { beg->first , social_graph->nodes[beg->first]->binf };
				com_topk.emplace_back(temp);
				break;
			}
			if (social_graph->nodes[beg->first]->binf < (++beg)->second) {
				kmax = Iteration(k - init_set.size() , init_set);
			}
			init_set.emplace(kmax.begin()->first);
			temp = { kmax.begin()->first , kmax.begin()->second };
			com_topk.emplace_back(temp);
			change_Binf(temp.first);
			kmax.pop_front();
		}
	}

	void change_Binf(int nodeId) {
		for (auto num : social_graph->nodes[nodeId]->canInfulence) {
			for (auto iter : social_graph->nodes[num]->beInfluence) {
				social_graph->nodes[iter]->binf--;
			}
			social_graph->nodes[num]->beInfluence.clear();
		}
	}

	std::list<std::pair<int, int>> Iteration(int k, set<int>& init_set) { 
		std::list< std::pair<int, int> > kmax;
		int size = 0;
		for (int index = 0; index < social_graph->node_num; index ++) {
			if (init_set.find(index) != init_set.end()) continue;
			if (size < k) {
				insertToList(kmax, { index , social_graph->nodes[index]->binf }); 
				size++;
				continue;
			}

			auto last = kmax.end();
			last--;
			if (last->second >= social_graph->nodes[index]->binf) {
				continue;
			}
			insertToList(kmax, { index , social_graph->nodes[index]->binf });
			kmax.pop_back();  
		}
		return kmax;
	}

	void insertToList(std::list<std::pair<int, int>>& kmax, pair<int, int> cur) {
		if (kmax.empty()) {
			kmax.emplace_back(cur);
			return;
		}
		auto beg = kmax.begin();
		while (beg != kmax.end()) {
			if (cur.second > beg->second) {
				kmax.emplace(beg, cur);
				break;
			}
			beg++;
		}
		if (beg == kmax.end()) {
			kmax.emplace(beg, cur);
		}
	}
};